# nums = [100,4,200,1,3,2]
# nums = [0,3,7,2,5,8,4,6,0,1]
# nums=[]
nums = [0, 1, 2, 4, 8, 5, 6, 7, 9, 3, 55, 88, 77, 99, 999999999]


# 连续的最长序列
# 先写一个比较容易的解决方法
# 该方法非常粗糙，肯定会超时
def longestConsecutive(nums):
    # 创建字典
    dictionary = dict()
    minVal = None
    maxVal = None
    for num in nums:
        dictionary[num] = True
        if minVal == None or minVal > num:
            minVal = num
        if maxVal == None or maxVal < num:
            maxVal = num
    ans = 0
    while minVal <= maxVal:
        count = 0
        while minVal in dictionary:
            minVal += 1
            count += 1
        if ans < count:
            ans = count
        minVal += 1
    print(ans)


# 先排序，再计算
def longestConsecutive1(nums):
    nums.sort()
    count = 0
    ans = 0
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1] - 1:
            count += 1
        else:
            if ans < count:
                ans = count
            count = 0
    return max(ans, count) + 1


# 用例：[0,1,2,4,8,5,6,7,9,3,55,88,77,99,999999999]会超时
# 时间复杂度为o(n^2)
def longestConsecutive2(nums):
    if len(nums) <= 1:
        return len(nums)
    numSet = set()
    minVal = None
    maxVal = None
    for num in nums:
        numSet.add(num)
        if minVal == None or minVal > num:
            minVal = num
        if maxVal == None or maxVal < num:
            maxVal = num
    print(numSet)
    count = 0
    ans = 0
    while minVal <= maxVal:
        if minVal in numSet:
            count += 1
            minVal += 1
        else:
            if ans < count:
                ans = count
            count = 0
            minValCur = minVal
            for num in nums:
                if minVal == minValCur and num > minVal:
                    minVal = num
                if minVal != minValCur and num > minValCur and num < minVal:
                    minVal = num

    ans = max(ans, count)
    return ans


def longestConsecutive3(nums):
    if len(nums) <= 1:
        return len(nums)
    numSet = set()
    minVal = None
    maxVal = None
    for num in nums:
        numSet.add(num)
        if minVal == None or minVal > num:
            minVal = num
        if maxVal == None or maxVal < num:
            maxVal = num
    print(numSet)
    count = 0
    ans = 0
    while minVal <= maxVal:
        if minVal in numSet:
            count += 1
            numSet.remove(minVal)
            minVal += 1
        else:
            if ans < count:
                ans = count
            count = 0
            minValCur = minVal
            for num in numSet:
                if minVal == minValCur:
                    minVal = num
                if minVal != minValCur and num > minValCur and num < minVal:
                    minVal = num
    ans = max(ans, count)
    print(ans)


def longestConsecutive4(nums):
    res = 0
    hash_dict = dict()
    for num in nums:
        # 新进来哈希表一个数
        if num not in hash_dict:
            # 获取当前数的最左边连续长度,没有的话就更新为0
            left = hash_dict.get(num - 1, 0)
            # 同理获取右边的数
            right = hash_dict.get(num + 1, 0)
            """不用担心左边和右边没有的情况
            因为没有的话就是left或者right  0
            并不改变什么
            """
            # 把当前数加入哈希表，代表当前数字出现过
            hash_dict[num] = 1
            # 更新长度
            length = left + 1 + right
            res = max(res, length)
            # 更新最左端点的值，如果left=n存在，那么证明当前数的前n个都存在哈希表中
            hash_dict[num - left] = length
            # 更新最右端点的值，如果right=n存在，那么证明当前数的后n个都存在哈希表中
            hash_dict[num + right] = length
            # 此时 【num-left，num-right】范围的值都连续存在哈希表中了
            # 即使left或者right=0都不影响结果
    return res


def longestConsecutive5(nums):
    dictionary=dict()
    maxLen=0
    for i in range(len(nums)):
        if nums[i] not in dictionary:
            #不在哈希表中
            #取得当前数左边数的长度
            left=dictionary.get(nums[i]-1,0)
            #右边
            right=dictionary.get(nums[i]+1,0)
            #当前数的长度
            curLength=left+right+1
            if curLength>maxLen:
                maxLen=curLength

            dictionary[nums[i]]=curLength
            dictionary[nums[i]-left]=curLength
            dictionary[nums[i]+right]=curLength
    return maxLen
    pass
print(longestConsecutive5(nums))